/*!
 Temelia - Stack samples.

 Copyright (C) 2008 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/samples.h"
#include <temelia/stack.h>

static int priority(char c);
struct my_struct;
struct term;
static void key_handler(void *key, void *fout);
static void sample1();
static void sample2();
static void sample3();
static void sample4();
static int my_strlen(char *str);

struct my_struct
{
	int d;
	float f;
	char c;
};

struct term
{
	double value;

	char operator;

	int type;
};

typedef struct my_struct *mystr;
typedef struct term *termen;

static termen *prefix_to_postfix(termen *data, int number, int *postfixnumber);
static double evaluate_postfix_expression(termen *data, int number);
static termen *parse_expression(char *expr, int *number);
static termen duplicate(termen data);

static void key_handler(void *key, void *fout)
{
	mystr st = (mystr) key;
	PRINT("%c %d %f\n", st->c, st->d, st->f);
}

static void sample1()
{
	stack_t s;
	mystr add;
	int i;

	PRINT("\n\n Sample 1 started \n\n");

	s = stack_new(10);
	for (i = 0; i < 25; i++)
	{
		add = (struct my_struct *) malloc(sizeof(struct my_struct));
		add->c = 'A' + rand() % 10;
		add->d = rand() % 15;
		add->f = (float) (rand() % 15);

		stack_push(s, add);
	}

	stack_iterate(s, key_handler, NULL, 1);

	// Although keys are not int pointers
	// this delete pointers iteration works
	// because it's a simple wrapper over free
	// standard function
	stack_iterate(s, int_delete, NULL, 1);

	stack_delete(s);

	PRINT("\n\n Sample 1 ended \n\n");
}

static void sample2()
{
	stack_t s;
	int i, *x;

	PRINT("\n\n Sample 2 started \n\n");

	s = stack_new(5);
	stack_set_capacity_increment(s, 0);

	for (i = 0; i < 25; i++)
	{
		x = (int *) malloc(sizeof(int));
		x[0] = i;
		stack_push(s, x);

		if (temelia_errno == FULL)
			free(x);
	}

	PRINT("Size/Capacity/Capacity Increment: %d %d %d\n", stack_get_size(s),
			stack_get_capacity(s), stack_get_capacity_increment(s));

	while (!stack_is_empty(s))
	{
		x = stack_top(s);
		int_handler(x, NULL);
		free(x);
		stack_pop(s);
	}

	stack_delete(s);

	PRINT("\n\n Sample 2 ended \n\n");
}

static void sample3()
{
	int *x, i;
	stack_t s;

	PRINT("\n\n Sample 3 started \n\n");

	s = stack_new(10);
	i = 0;

	while (!stack_is_full(s))
	{
		x = (int *) malloc(sizeof(int));
		x[0] = i;
		stack_push(s, x);
	}

	while (!stack_is_empty(s))
	{
		x = stack_top(s);

		int_handler(x, NULL);
		free(x);

		stack_pop(s);
	}

	stack_delete(s);

	PRINT("\n\n Sample 3 ended \n\n");
}

static double evaluate_postfix_expression(termen *data, int number)
{
	stack_t s;
	double value;
	int i;
	termen x, y, z;

	s = stack_new(number);
	for (i = 0; i < number; i++)
	{
		if (data[i]->type == 1)
		{
			if (data[i]->operator == '+')
			{
				y = (termen) stack_top(s);
				stack_pop(s);

				x = (termen) stack_top(s);
				stack_pop(s);

				z = (struct term *) malloc(sizeof(struct term));
				z->type = 0;
				z->value = x->value + y->value;

				stack_push(s, z);

				free(x);
				free(y);
			}
			else if (data[i]->operator == '-')
			{
				y = (termen) stack_top(s);
				stack_pop(s);
				x = (termen) stack_top(s);
				stack_pop(s);

				z = (struct term *) malloc(sizeof(struct term));
				z->type = 0;
				z->value = x->value - y->value;
				stack_push(s, z);
				free(x);
				free(y);
			}
			else if (data[i]->operator == '*')
			{
				y = (termen) stack_top(s);
				stack_pop(s);
				x = (termen) stack_top(s);
				stack_pop(s);

				z = (struct term *) malloc(sizeof(struct term));
				z->type = 0;
				z->value = x->value * y->value;
				stack_push(s, z);
				free(x);
				free(y);
			}
			else if (data[i]->operator == '/')
			{
				y = (termen) stack_top(s);
				stack_pop(s);
				x = (termen) stack_top(s);
				stack_pop(s);

				z = (struct term *) malloc(sizeof(struct term));
				z->type = 0;
				if (y->value == 0)
				{
					PRINT("DIVISION BY 0 !\n");
					exit(0);
				}
				z->value = x->value / y->value;
				stack_push(s, z);
				free(x);
				free(y);
			}
		}
		else
		{
			z = (struct term *) malloc(sizeof(struct term));
			z->type = 0;
			z->value = data[i]->value;
			stack_push(s, z);
		}
	}
	x = (termen) stack_top(s);
	value = x->value;
	stack_delete(s);
	free(x);
	return value;
}

termen *prefix_to_postfix(termen *data, int number, int *postfixnumber)
{
	termen *postfix;
	int i, k;
	termen x;
	stack_t s;

	s = stack_new(number);
	k = 0;
	postfix = (termen *) malloc(number * sizeof(termen));

	for (i = 0; i < number; i++)
	{
		if (data[i]->type == 1)
		{

			x = (termen) stack_top(s);

			if (x != NULL)
			{
				while (priority(data[i]->operator) <= priority(x->operator))
				{
					stack_pop(s);
					postfix[k++] = duplicate(x);
					x = (termen) stack_top(s);
					if (x == NULL)
						break;
				}
			}
			stack_push(s, data[i]);
		}

		else if (data[i]->type == 2)
			stack_push(s, data[i]);

		else if (data[i]->type == 3)
		{
			x = (termen) stack_top(s);
			if (x != NULL)
			{
				while (x->type != 2)
				{
					postfix[k++] = duplicate(x);
					stack_pop(s);
					x = stack_top(s);
					if (x == NULL)
						break;
				}
			}
			stack_pop(s);
		}
		else if (data[i]->type == 0)
			postfix[k++] = duplicate(data[i]);
	}

	while (!stack_is_empty(s))
	{
		x = (termen) stack_top(s);
		stack_pop(s);
		postfix[k++] = duplicate(x);
	}

	stack_delete(s);
	*postfixnumber = k;

	return postfix;
}

int priority(char c)
{
	if (c == '+' || c == '-')
		return 2;
	if (c == '*' || c == '/')
		return 3;
	if (c == '(' || c == ')')
		return 1;
	return 0;
}

int my_strlen(char *str)
{
	int i = 0;

	while (str[i++])
		;

	return i;
}

termen duplicate(termen data)
{
	return data;
}

termen *parse_expression(char *expr, int *number)
{
	int i = 0, k = 0, len;
	termen *data;
	*number = 0;
	len = my_strlen(expr);
	while (i < len)
	{
		if (priority(expr[i]))
			*number += 2;
		else if (expr[i] == '(' || expr[i] == ')')
			*number += 1;
		i++;
	}
	*number += 1;

	data = (termen *) malloc((*number) * sizeof(termen));
	for (i = 0; i < *number; i++)
		data[i] = (struct term *) malloc(sizeof(struct term));

	i = 0;
	while (i < len)
	{
		if (expr[i] == '(')
		{
			data[k]->type = 2;
			data[k]->operator = '(';
			data[k]->value = 0;
			k++;
		}
		else if (expr[i] == ')')
		{
			data[k]->type = 3;
			data[k]->operator = ')';
			data[k]->value = 0;
			k++;
		}
		else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '/' || expr[i]
				== '*')
		{
			data[k]->type = 1;
			data[k]->operator = expr[i];
			data[k]->value = 0;
			k++;
		}
		else if ('0' <= expr[i] && expr[i] <= '9')
		{
			data[k]->type = 0;
			data[k]->operator = ';';
			data[k]->value = expr[i] - '0';
			i++;
			while ('0' <= expr[i] && expr[i] <= '9')
			{
				data[k]->value = data[k]->value * 10 + (expr[i] - '0');
				i++;
			}
			k++;
			i--;
		}
		i++;
	}
	for (i = k; i < *number; i++)
		free(data[i]);
	*number = k;
	return data;
}

static void sample4()
{
	termen *data, *postfixdata;
	char *expression = "3*2+(2+18)/5";
	int number, postfixnumber, i;

	PRINT("\n\n Sample 4 started \n\n");

	data = parse_expression(expression, &number);
	postfixdata = prefix_to_postfix(data, number, &postfixnumber);

	PRINT("Evaluating %s\n\n", expression);
	PRINT("The result is :\n%lf", evaluate_postfix_expression(postfixdata,
					postfixnumber));

	for (i = 0; i < number; i++)
		free(data[i]);
	free(data);
	free(postfixdata);

	PRINT("\n\n Sample 4 ended \n\n");
}

void run_stack_samples()
{
	sample1();
	sample2();
	sample3();
	sample4();
}
